/*
 * Copyright (C), 2015-2018
 * FileName: Solution141
 * Author:   zhao
 * Date:     2018/9/11 15:51
 * Description: 141. 环形链表
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.hundredtwo;

import com.lizhaoblog.diynode.ListNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 〈一句话功能简述〉<br>
 * 〈141. 环形链表〉
 *
 * @author zhao
 * @date 2018/9/11 15:51
 * @since 1.0.1
 */
public class Solution141 {
  /**************************************
   * 题目
   给定一个链表，判断链表中是否有环。

   进阶：
   你能否不使用额外空间解决此题？
   **************************************/

  /**************************************
   *
   * 想法：
   *    1. 额外添加一个数组
   *      遍历链表
   *      判断是否存在在数组之中
   *
   *    2. 双指针法
   *      想象成2个小人赛跑，一个前进一格，一个前进2格
   *      这样总会相交，这时候判断有无环
   * 我的做法
   *      超过  %的测试案例
   *
   * 代码执行过程：
   *
   * 总结：
   *    1. 第一种方法，没有看题目，额外添加了空间
   * ***********************************/
  public boolean hasCycle(ListNode head) {
    if (head == null) {
      return false;
    }

    List<ListNode> listNodes = new ArrayList<>();
    listNodes.add(head);

    boolean needStop = false;
    boolean hsaCycle = false;

    ListNode nowNode = head;

    while (!needStop) {
      nowNode = nowNode.next;
      if (nowNode == null) {
        needStop = true;
        continue;
      }
      int index = listNodes.indexOf(nowNode);
      if (index > -1) {
        hsaCycle = true;
        needStop = true;
        continue;
      }
      listNodes.add(nowNode);
    }

    return hsaCycle;
  }

  /**************************************
   * 比我好的答案 better
   * ***********************************/
  public boolean better(ListNode head) {
    if (head == null || head.next == null) {
      return false;
    }

    ListNode pre = head;
    ListNode cur = head;

    while (pre != null && pre.next != null && pre.next.next != null) {
      cur = cur.next;
      pre = pre.next.next;
      if (pre == cur) {
        return true;
      }
    }
    return false;
  }

}
